/**
 * This file is part of Sonedyan.
 * 
 * Sonedyan is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation;
 * either version 3 of the License, or (at your option) any
 * later version.
 *
 * Sonedyan is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public
 * License along with Octave; see the file COPYING.  If not
 * see <http://www.gnu.org/licenses/>.
 * 
 * Copyright (C) 2009-2013 Jimmy Dubuisson <jimmy.dubuisson@gmail.com>
 */

package org.unige.mpej.eckmann.sonedyan.mr;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

import org.apache.log4j.Logger;

public class ComponentsFinder
{
	private static Logger log = Logger.getLogger(org.unige.mpej.eckmann.sonedyan.mr.ComponentsFinder.class);
	
	private static enum Color {WHITE, GREY, BLACK}
	
	/**
	 * vertex data
	 */
	private class VertexData
	{
		
		public Color color;
		public int firstParent;
		public int lowReverseIndex;
		public int lowIndex;
		
		public VertexData()
		{
			this.color = Color.WHITE;
		}
	}
	
	private LocalGraphLoader loader;
	
	// set of remaining nodes after a shave phase
	private HashSet<Integer> connected;
	
	/**
	 * constructor
	 */
	public ComponentsFinder(LocalGraphLoader loader)
	{
		this.loader = loader;
	}
	
	public boolean shave()
	{
		boolean removed = false;
		
		log.info("Shaving...");
		
		Set<Integer> indexV = this.loader.index.keySet();
		
		log.info("# indices: " + indexV.size());
		log.info("nextVertex size: " + this.loader.nextVertex.size());
		log.info("Getting children...");
		
		HashSet<Integer> children = new HashSet<Integer>();
		
		for (int i = 0; i < this.loader.data.length; i++)
		{
			int c = this.loader.data[i];
			
			if (c != -1)
				children.add(c);
		}
		
		log.info("Getting connected vertices...");
		
		this.connected = new HashSet<Integer>(indexV);
		this.connected.retainAll(children);
		
		log.info("# connected vertices: " + this.connected.size());
		
		log.info("Getting sinks...");
		
		Set<Integer> sinks = null;
		
		if (children.size() > connected.size())
		{
			sinks = children;
			sinks.removeAll(connected);
			
			log.info("# sinks: " + sinks.size());
			removed = true;
		}
		else
		{
			log.info("No sink found");
		}
		
		log.info("Getting sources...");
		
		Set<Integer> sources = null;
		
		if (indexV.size() > connected.size())
		{
			sources = new HashSet<Integer>(indexV);
			sources.removeAll(connected);
			
			log.info("# sources: " + sources.size());
			removed = true;
		}
		else
		{
			log.info("No source found");
		}
		
		// remove sources from index, sinks from children and regenerating nextV
		if (removed)
		{
			Set<Integer> dangling = null;
			
			// there are some sinks
			if (sinks != null)
			{
				log.info("Removing " + sinks.size() + " sinks from data");
				
				// update data
				for (int i = 0; i < this.loader.data.length; i++)
				{
					if (sinks.contains(this.loader.data[i]))
					{
						this.loader.data[i] = -1;
					}
				}
				
				// remove dangling indices
				dangling = this.loader.getDanglingIndices();
				
				log.info(dangling.size() + " dangling nodes found in index");
			}
			
			// there are sources
			if (sources != null)
			{
				log.info("Removing children of " + sources.size() + " sources from data");
				
				// remove source vertices children from data
				for (int v: sources)
				{
					this.loader.removeSourceVertexChildren(v);
				}
				
				// regenerate nextVertex
				HashMap<Integer,Integer> nextVertex = new HashMap<Integer, Integer>();
				
				log.info("updating nextV");
				log.info("Current first vertex is: " + this.loader.firstVertex);
				
				ArrayList<Integer> lV = new ArrayList<Integer>();
				int currentV = this.loader.firstVertex;
				boolean firstUpdated = false;
				Integer nextV;
				
				Set<Integer> toBeRemoved = new HashSet<Integer>(sources);
				
				if (dangling != null && dangling.size() > 0)
				{
					toBeRemoved.addAll(dangling);
				}
				
				log.info(toBeRemoved.size() + " vertices (sources+dangling) to be removed");
				
				while ((nextV = this.loader.nextVertex.get(currentV)) != null)
				{
					if (!toBeRemoved.contains(currentV))
					{
						lV.add(currentV);
						
						if (!firstUpdated)
						{
							this.loader.firstVertex = currentV;
							firstUpdated = true;
						}
					}
					
					currentV = nextV;
				}
				
				if (!toBeRemoved.contains(currentV))
				{
					lV.add(currentV);
					
					if (!firstUpdated)
					{
						this.loader.firstVertex = currentV;
					}
				}
				
				for (int i = 0; i < lV.size() - 1; i++)
				{
					nextVertex.put(lV.get(i), lV.get(i+1));
				}
				
				nextVertex.put(lV.get(lV.size()-1), null);
				this.loader.nextVertex = nextVertex;
				
				log.info("Updated nextVertex size: " + nextVertex.size());
				log.info("Updated first vertex is: " + this.loader.firstVertex);
				
				log.info("Removing " + sources.size() + " sources from index");
				
				// remove sources from index
				for (int v: sources)
				{
					this.loader.index.remove(v);
				}
				
				log.info("Removing " + dangling.size() + " dangling nodes from index");
				
				// remove dangling nodes from index
				if (dangling != null && dangling.size() > 0)
				{
					for (int i: dangling)
					{
						this.loader.index.remove(i);
					}
				}
	
				log.info("Updated # of indices: " + this.loader.index.size());
			}
			
			log.info("data array successfully updated");
		}
		
		return removed;
	}
	
	/**
	 * shave as long as necessary
	 */
	public void shaveAll()
	{
		boolean goOn = true;
		
		while(goOn)
		{
			log.info("----------");
			goOn = this.shave();
			log.info("----------");
		}
		
		log.info("shaving phase has completed successfully");
	}
	
	/**
	 * main method
	 */
	public static void main(final String[] args) throws Exception
	{
		LocalGraphLoader loader = new LocalGraphLoader();
		// BufferedWriter bw = new BufferedWriter(new FileWriter("twitter-sccs.txt"));

		ComponentsFinder cFinder = new ComponentsFinder(loader);
		cFinder.shaveAll();
	}
	
}
